package datastructure.linklist;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/12 13:31
 * @description:
 */
public class MyLinkedList {
    int size;
    ListNode head;

    public MyLinkedList() {
        this.size = 0;
        this.head = new ListNode(-1);
    }

    public int get(int index) {
        // 索引无效（超出范围）
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode p = head;
        for (int i = 0; i <= index; i++) {
            if (p != null) {
                p = p.next;
            }
        }
        if (p != null) {
            return p.val;
        }
        return -1;
    }

    public void addAtHead(int val) {
        ListNode p = new ListNode(val);
        p.next = head.next;
        head.next = p;
        size++;
    }

    public void addAtTail(int val) {
        ListNode p = head;
        while (p.next != null) {
            p = p.next;
        }
        p.next = new ListNode(val);
        size++;
    }

    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) {
            return;
        }
        ListNode p = head;
        for (int i = 0; i < index; i++) {//p指向index-1的位置
            p = p.next;
        }
        ListNode data = new ListNode(val);
        data.next = p.next;
        p.next = data;
        size++;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        ListNode p = head;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        p.next = p.next.next;
        size--;
    }

    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        ListNode head = myLinkedList.head;
        myLinkedList.addAtHead(1);
        ListNode.printList(head);
        myLinkedList.addAtTail(3);
        ListNode.printList(head);
        myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
        ListNode.printList(head);
        myLinkedList.get(1);              // 返回 2
        myLinkedList.deleteAtIndex(0);    // 现在，链表变为 1->3
        ListNode.printList(head);
        myLinkedList.get(1);              // 返回 3
    }

    public static class ListNode {
        public ListNode pre;
        public ListNode next;
        public int val;

        public ListNode(ListNode pre, ListNode next, int val) {
            this.pre = pre;
            this.next = next;
            this.val = val;
        }

        public ListNode(ListNode next, int val) {
            this.next = next;
            this.val = val;
        }

        public ListNode(int val) {
            this.val = val;
        }

        public static void printList(ListNode head) {
            if (head == null) {
                System.out.println("null"); // 空链表直接打印null
                return;
            }

            ListNode current = head;
            StringBuilder sb = new StringBuilder();

            // 拼接链表节点值
            while (current != null) {
                sb.append(current.val);
                if (current.next != null) {
                    sb.append(" -> ");
                }
                current = current.next;
            }

            System.out.println(sb.toString());
        }

    }
}
